"""
解题思路
这是一道基于前缀和的题目，我们简单来说一下思路。
如果我们采用传统的方法，即对所有数组求累积，然后除以当前位置的值得到结果；这样的方法是不可行的
其原因是，如果当前元素为0，无法计算。

所以这道题自然而然的需要用前缀和的方式求解。
同时需要注意，该算法需要双向的前缀和，即第N位的元素值应当是N之前的元素乘积和N之后的元素乘积
所以需要双重遍历。

最后合并一下就可以得到结果了。

"""


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = [1]
        suffix = [1]
        for i in nums:
            prefix.append(prefix[-1] * i)
        
        for i in nums[::-1]:
            suffix.append(suffix[-1] * i)

        suffix = suffix[::-1]

        return [prefix[i] * suffix[i+1] for i in range(len(nums))]
